function [dist, path] = floydWarshall(w)
    n = size(w, 1);
    dist = w;
    path = zeros(n, n);

    % Initialize distance and path matrices
    for i = 1:n
        for j = 1:n
            if i ~= j && w(i, j) == inf
                path(i, j) = 0; % No direct edge between i and j
            else
                path(i, j) = i; % Direct edge from i to j
            end
        end
    end

    % Floyd-Warshall algorithm
    for k = 1:n
        for i = 1:n
            for j = 1:n
                if dist(i, k) + dist(k, j) < dist(i, j)
                    dist(i, j) = dist(i, k) + dist(k, j);
                    path(i, j) = path(k, j);
                end
            end
        end
    end
end